1619H - Permutation and Queries - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5, B = 300;
int n, q, p[MAXN], a[MAXN], r[MAXN];

int main() {
	
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> p[i];
		r[p[i]] = i;
	}
	for (int i = 1; i <= n; i++) {
		int c = i;
		for (int j = 0; j < B; j++) {
			c = p[c];
		}
		a[i] = c;
	}
	for (int i = 0; i < q; i++) {
		int t;
		cin >> t;
		if (t == 1) {
			int x, y;
			cin >> x >> y; 
			r[p[x]] = y;
			r[p[y]] = x;
			swap(p[x], p[y]);
			int c = x;
			for (int j = 0; j < B; j++) {
				c = p[c];
			}
			int l = x;
			a[l] = c;
			for (int j = 0; j < B; j++) {
				l = r[l];
				c = r[c];
				a[l] = c;
			}
			c = y;
			for (int j = 0; j < B; j++) {
				c = p[c];
			}
			l = y;
			a[l] = c;
			for (int j = 0; j < B; j++) {
				l = r[l];
				c = r[c];
				a[l] = c;
			}
		}
		else {
			int x, k;
			cin >> x >> k;
			int ans = x;
			for (int j = 0; j < k / B; j++) {
				ans = a[ans];
			}
			for (int j = 0; j < k - B * (k / B); j++) {
				ans = p[ans];
			}
			cout << ans << '\n';
		}
	}
}